前言

昨天介紹了一些基於粒子的演算法，他們都是將生物群體比喻為粒子並根據不同的行為得到啟發而開發出這些演算法。今天要介紹的是基於進化策略的演算法，隨著地球這幾千萬年的變化，地球上的生物透過演化進化成了最適合當代條件下生存的物種。而基於進化的演算法就是基於這些原理進行最佳化，找出適應值(fitness)最高的解(物種)。

基因演算法(Genetic Algorithms, GA)

與粒子群最佳化演算法(PSO)一樣基礎、一樣廣為人知的演算法，GA和PSO有著完全不同的機制，透過**突變(Mutation)**這樣的機制來盡量避免陷入局部最佳解，為演算結果新增了一些變數，GA就類似於生物繁衍時的基因遺傳等概念，接下來就來看看GA的原理吧。

概念

GA的概念很簡單，大致上只有四個步驟，分別是評估(Evaluation)、選擇(Selection)、交配(Crossover)、突變，大致上GA就是重複這四個步驟而逐漸將適合的結果保留，不適合的結果淘汰掉，相當於達爾文的天擇說。接下來我將大致簡述基因演算法的這幾個步驟，基本上GA演算法網路上非常多的教學，問GPT應該也能得到大致正確的結果。[參考文章1]、[參考文章2]

1. 初始化：和大多數演算法一樣，GA演算法也要進行初始化並設定一些數值以及變數。初始化所需的東東有染色體，和昨天的粒子不同，昨天以粒子來形容各種要帶入問題的解，而今天GA是以染色體當作要帶入問題的解。每條染色體都是一個相同長度的向量，內容就是要帶入問題的那些因素。
2. 評估：首先初始化後會隨機產生初始的染色體們，這些染色體和昨天介紹的那些粒子一樣，因為不知道問題的分布所以初始生成都是完全隨機的。生成之後的染色體們會根據自身的資訊計算出適應值(fitness value)。
3. 選擇：為了演化出更加優良的「後代」，GA會從最一開始的染色體們中尋找優秀的染色體，選擇的方法會採用輪盤法，簡單來說就是每個染色體的適應值高低會成為被選擇的機率高低。除此之外也有其他選擇法被使用，例如菁英挑選法，使用這個方法就是能保證最優秀的幾個結果會被保留下來。
4. 交配：交配會根據機率來決定，如果隨機變數的值小於交配閥值則會進行交配，交配方法會依照隨機數決定斷點，接著根據此斷點將兩個染色體都切成兩部分並重新組合成新的染色體。
5. 突變：突變也會根據機率發生，若隨機數低於設定的突變率閥值的話則會突變，突變方式很簡單，隨機挑選染色體中的幾個內容中數值的位元，並將隨機位元的0與1進行對調，這些數值資料中變為二進制之後隨機突變就會有一種與原來資料似是而非的感覺。這步驟完成後基本上染色體就會變得跟初始的染色體不同的一群新的染色體了。
6. 重複第2.步到第5.步，直到迭代結束，迭代結束後就輸出最佳的解。

總評

GA作為啟發式演算法入門必學的一個演算法，它的優點就是容易上手、速度快，但有時也不可避免的容易陷入局部最佳解，依靠微小的突變機率又剛好突變到適合的位置更佳的不容易TT，另外因為適應值會重複計算，所以像在AI模型最佳化時重新計算類似結果就會造成運算資源不必要的浪費。不過以GA為基礎的演算法也有許多被研發出來，對於不同的應用也算是有不同的使用方式。

珊瑚礁演算法(Coral Reefs Optimization, CRO)

珊瑚礁演算法是2013年被提出的演算法，作者受到珊瑚蟲繁衍生存過程中的啟發而創造的演算法。

概念與原理

珊瑚礁演算法就是根據珊瑚蟲繁衍的方式去設計的，各位有興趣可以去看看珊瑚蟲繁衍的壯闊景象。這個演算法基本上也是幾個步驟循環而找到比較好的解。

1. 初始化：老套的初始化，CRO的初始化會假設一個珊瑚礁，這個珊瑚礁會有很多空間給珊瑚蟲生存，空間數量為N，那各位可能會好奇珊瑚蟲的數量呢？其實初始化還要設定空間中有珊瑚蟲居住的比例p，所以珊瑚蟲數量是p×N。和GA等演算法類似，CRO是以珊瑚蟲來當作要代入問題的解。
2. 珊瑚蟲的有性繁殖：這部分分成兩個繁殖方式，有性繁殖與無性繁殖。有性繁殖又分為珊瑚礁外部的有性生殖與珊瑚礁內部的有性生殖，接下來我會來分別介紹這兩種生殖方式。首先會將珊瑚蟲分為外部與內部的珊瑚蟲。
   • 珊瑚礁外部的有性生殖：這部分會將外部的珊瑚蟲直接隨機產生一些子代。
   • 珊瑚礁內部的有性生殖：這部分會先將內部珊瑚蟲分成兩個群體，公珊瑚蟲與母珊瑚蟲。接著公母珊瑚蟲會類似GA那樣進行交配產生新的子代。
3. 更替珊瑚蟲：這步驟會讓所有新的珊瑚蟲去找珊瑚礁中還沒被佔領的空間，如果該空間沒珊瑚蟲則該子代就可以直接佔領；若該空間有珊瑚蟲則需要比較適應值，適應值高的珊瑚蟲可以入住該空間，適應值低的則會被趕出來(有點心酸)。子代的珊瑚蟲會嘗試幾次佔領，若經過特定次數還沒佔領成功就會死亡。能夠嘗試多次佔領是因為如果只能一次定生死的話，那有可能第二高的珊瑚蟲就直接被第一高的珊瑚蟲幹掉了，白白損失一個優秀「蟲」才。
4. 珊瑚蟲的無性繁殖：當珊瑚礁所有空間都被佔領時，則根據特定比例選出一些高適應值的珊瑚蟲，並進行無性繁殖的方式複製出子代來並進行珊瑚礁的占據，也就是進行第3步驟。
5. 淘汰弱小的珊瑚蟲：此步驟比較殘忍，會根據特定比例選出一些低適應值的珊瑚蟲並進行「人道毀滅」，藉此將珊瑚礁騰出一些空間來供下一次迭代使用。完成後算一次迭代，迭代次數+1。
6. 重複步驟2.到步驟5.值到迭代結束，並輸出整個群體的最佳解以及適應值。

總評

因為內部有性生殖的部分和GA一樣，透過交配產生新子代會導致最佳化方向是比較隨機的，不像基於粒子的演算法會有一個優化方向，這會使CRO的最佳化不容易收斂(GA也一樣)，這類型演算法太依賴初代的能力了。且CRO目前是直接讓適應值高的珊瑚蟲取代適應值低的珊瑚蟲，這會比較不利於種群的多樣性，非常容易陷入局部最佳解。
不過目前有很多研究用於針對這些問題提出改良方法，例如借鑑PSO的優化方向，將更替珊瑚蟲加入一些機制，目前由CRO延伸出來的演算法能力有比較好，也可以跳出局部最佳解的位置去尋找其他解。
參考資料

結語

今天分享了幾個基於進化的演算法，明天會繼續分享其他概念的最佳化演算法，基於進化的演算法目前來說比較少見，因為進化過程中大方向都是類似的，並不像不同物種有不同行為那樣比較好受到啟發。但目前進化為基礎的演算法像GA等都有不少的變種演算法，或多或少都做了一些微調並更加契合研究的主題根所需的功能。